#include <iostream>
using namespace std;

typedef struct BiTNode {
    TElemType data;     // 结点数据域
    struct BiTNode *lchild, *rchild;    // 左右孩子指针
}BiTNode, *BiTree;

void visit(BiTree T) {
    cout << T->data;
}

bool PreOrderTraverse(BiTree T)
{
    if (T == NULL) return ture;	// 空二叉树
    else {
        visit(T);	 // 访问根节点
        PreOrderTraverse(T->lchild);
    	PreOrderTraverse(T->rchild);
    }
}

bool InOrderTraverse(BiTree T)
{
    if (T == NULL) return ture;	// 空二叉树
    else {
        PreOrderTraverse(T->lchild);
        visit(T);	
    	PreOrderTraverse(T->rchild);
    }
}

bool PostOrderTraverse(Bitree T)
{
    if (T == NULL) return ture;	
    else {
        PreOrderTraverse(T->lchild);	
    	PreOrderTraverse(T->rchild);
        visit(T);
    }
}

// 非递归的中序遍历
bool InOrderTraverse(BiTree T) 
{
    BiTree p;
    InitStack(S);
    p = T;
    q = new BiTNode;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        }
        else {
            Pop(S, q);
            cout << q->data;
            p = q->rchild;
        }
    }
}

// 层序遍历 使用队列
typedef struct {
    BiTNode data[MaxSize];   // 存放队中元素
    int front, rear;        // 队头和队尾指针
} SqQueue;      // 顺序循环队列类型

void LevelOrder(BiTNode *b) {
    BiTNode *p; 
    SqQueue *qu;
    InitQueue(qu);  // 初始化队列
    enQueue(qu,b);  // 根结点指针进入队列
    while(!QueueEmpty(qu)) {    // 若队列不空，则循环
        deQueue(qu, p);    // 出队结点p
        cout << p->data;
        if (p->lchild != NULL)
            enQueue(qu, p->lchild);
        if (p->rchild != NULL)
            enQueue(qu, p->rchild);
    }
}

// 先序遍历建立二叉链表
bool CreateBiTree(BiTree &T) {
    cin >> ch;
    if (ch == "#") T = NULL:
    else {
        T = (BiTNode *)malloc(sizeof(BiTNode))
        T->data = ch;   // 生成根结点
        CreateBiTree(T->lchild);    // 构造左子树
        CreateBiTree(T->rchild);    // 构造右子树
    }
    return true;
}

// 复制二叉树
int Copy(BiTree T, BiTree &NewT) {
    if (T == NULL) {   // 如果是空树返回0
        NewT = NULL;
        return 0;
    }
    else {
        NewT = new BiTNode;
        NewT->data = T->data;
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }
}

// 计算二叉树的深度
int Depth(BiTree T) {
    if (T == NULL) return 0;    // 如果是空树返回0
    else {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if (m > n) return (m+1);
        else return (n+1);
    }
}

// 计算二叉树结点总数
int NodeCount(BiTree T) {
    if (T == NULL)  return 0;
    else 
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

// 计算二叉树叶子结点数
int LeafCount(BiTree T) {
    if (T == NULL)  return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return 1;
    else 
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}

int main(void) {
    
}